package sorting;

public class MergeSort
{
    private int[] myData;

    public MergeSort(int[] data)
    {
        myData = data;
    }
    public static void main(String[] args)
    {
        int[] data = new int[20];
        if (args.length > 20) {
            System.err.println("Not valid for more than 20 entries");
        }
        int i = 0;
        for (String s : args) {
            data[i++] = Integer.parseInt(s);    
        }

        MergeSort sorter = new MergeSort(data);
        System.out.println("Before sorting: " + sorter);
        System.out.println("length: " + data.length);
        sorter.sort(0, data.length - 1);
        System.out.println("After sorting: " + sorter);
        System.out.println(MergeSort.getNotes());
    }

    private void sort(int min, int max)
    {
        if (min < max) {
            StringBuilder sb = new StringBuilder("Sorting: ");
            for (int i = min; i <= max; i ++) {
                sb.append(myData[i] + " ");
            }
            System.out.println(sb.toString());
            int mid = (min + max)/2;
            sort(min, mid);
            sort(mid + 1, max);
            merge(min, mid, max);
        } 
    }

    private void merge(int min, int mid, int max)
    {
        StringBuilder sb = new StringBuilder("Merging: ");
        for (int i = min; i <= mid; i ++) {
            sb.append(myData[i] + " ");
        }
        
        StringBuilder sb1 = new StringBuilder();
        for (int i = mid + 1; i <= max; i ++) {
            sb1.append(myData[i] + " ");
        }
        System.out.println(sb.toString() + " and " + sb1.toString());
        
        int[] arr1 = new int[mid - min + 1];
        int[] arr2 = new int [max - mid];
        
        // Copy the first half.
        for(int k = 0; k <= mid -min; k ++) {
            arr1[k] = myData[min + k];
        }
        
        // Copy the second half.
        for(int k = 0; k <= max - mid - 1; k ++) {
            arr2[k] = myData[k + mid + 1];
        }
        
        int i = 0, j = 0, k = min;
        while(i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                myData[k++] = arr1[i];
                i++;
            }
            else {
                myData[k++] = arr2[j];
                j++;
            }
        }
        
        while (i < arr1.length) {
            myData[k++] = arr1[i++];
        }
        
        while (j < arr2.length) {
            myData[k++] = arr2[j++];
        }
        
        System.out.println("After merge: ");
        sb = new StringBuilder();
        for (int km = min; km <= max; km++) {
            sb.append(myData[km] + " ");
        }
        System.out.println(sb.toString());
    }
    
    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        for (int i : myData) {
            sb.append(i + " ");
        }

        return sb.toString();
    }

    public static String getNotes()
    {
        return "The worst case complexity is O(nlogn)";
    }


}
